13 Hard Limits of Computation

Algorithmics 2025

Origins of Computer Science

A History Lesson

Vocabulary

  • Axiom — foundational statement assumed true
  • Church–Turing thesis — defines the boundary of what is computable
  • Completeness
  • Computable — can be solved by a Turing machine
  • Consistent — no contradictions in the system
  • Decidable — algorithm exists that always halts with yes/no

Vocabulary

  • Entscheidungsproblem - Ent-shy-dungs-problem - decision problem posed by Hilbert
  • Finite — limited in size or length
  • Halting Problem — classic undecidable problem
  • Paradox — self-contradictory result (like Russell’s Paradox or the Liar Paradox)
  • Turing machine — model of computation
  • Undecidable — no such algorithm exists

The Players

  • David Hilbert (1862–1943)
    German mathematician. University of Göttingen in Germany.
  • Wilhelm Ackermann (1896–1962)
    Student and collaborator of Hilbert. University of Göttingen in Germany.
  • Alonzo Church (1903–1995)
    American logician. Princeton University in the USA.
  • Alan Turing (1912–1954)
    British mathematician and founder of computer science. University of Cambridge (UK).
    From 1936 to 1938, Turing went to Princeton to do his PhD under Alonzo Church.

Timeline of Publications

  • 1928
    Hilbert and Ackermann
    Grundzüge der theoretischen Logik (Principles of Mathematical Logic).
    They formalised first-order logic and clearly defined the Entscheidungsproblem (decision problem): whether there exists a general mechanical procedure (algorithm) to decide if any given statement is provable.

Timeline of Publications

  • 1936
    Alonzo Church
    “An Unsolvable Problem of Elementary Number Theory” published.
    Church used lambda calculus to prove that the Entscheidungsproblem is undecidable — showing that there is no general algorithm to decide provability for all statements in first-order logic.

Timeline of Publications

  • 1936
    Alan Turing
    “On Computable Numbers, with an Application to the Entscheidungsproblem” published.
    Turing introduced the Turing machine as a new model of computation.
    He proved the Halting Problem is undecidable, which implies that the Entscheidungsproblem is undecidable too.

The Story

  • In the early 20th century, mathematics faced a crisis due to logical paradoxes, such as Russell’s Paradox.
  • Hilbert proposed a solution: formalise all of mathematics using a set of axioms and rules. His goal was a symbolic system in which all mathematical truths could be derived mechanically — no intuition, just logic.

The Story

  • Ackermann worked with Hilbert to formalise logic and pose the Entscheidungsproblem: to find a single algorithm that could decide if a mathematical statement was true or false.
  • In 1936, Alonzo Church proved that the Entscheidungsproblem is undecidable, using a formal model of computation called lambda calculus.

The Story

  • Around the same time, Alan Turing independently proved the same result using his new model of computation — the Turing machine — by showing that the Halting Problem is undecidable.
  • Church and Turing’s work led to the formulation of the Church–Turing Thesis, the formal limit of what can be computed.

Some Details

Hilbert’s Program

Hilbert’s program aimed to reduce all of mathematics to formal symbolic manipulations.

Every line follows strictly from axioms and rules:

  • No intuition, no diagrams, no external meanings.

  • Just symbols and logic.

Hilbert’s Program

In his 1927 program to fully formalise mathematical reasoning, David Hilbert outlined the following three goals:

  1. Mathematics should be complete: all true mathematical statements can be derived from a finite set of axioms.
  2. Mathematics should be consistent: no contradictions.
  3. Mathematics should be decidable: proofs can be verified by a single algorithm.

Example – not on study design

Peano and Addition Axioms

  1. ( 0 ) Zero is a natural number.

  2. ( x , S(x) ) Every natural number has a successor.

  3. ( x , S(x) ) Zero is not the successor of any number.

  4. ( x, y , S(x) = S(y) x = y ) The successor function is injective (no two numbers share a successor).

  5. ( x , x + 0 = x ) Zero is the additive identity.

  6. ( x, y , x + S(y) = S(x + y) ) Defines addition recursively using the successor function.

Classic physics as Example

  • The finite set of axioms: Newton’s three laws of motion and the Law of Universal Gravitation.

Key equations:

\[ \text{Newton's Second Law:} \quad F = ma \]

\[ \text{Law of Universal Gravitation:} \quad F = G \frac{m_1 m_2}{r^2} \]

Classic physics as Example

From just these axioms, you can:

  • Predict the orbit of Earth around the Sun (Kepler’s laws).
  • Calculate the trajectory of a rocket.
  • Explain phenomena like tides.

Classic physics as Example

The laws act like a formal system:

  • They are finite (a few basic laws).
  • They are consistent (no contradictions).
  • They are decidable for simple systems (you can solve the equations exactly).

Where Limits Appear

However, as systems become more complex:

  • Many-body problems become chaotic.
  • Exact solutions may be impossible; only approximations exist.
  • Quantum mechanics introduces inherent uncertainty.

Entscheidungsproblem

The Entscheidungsproblem posed by Hilbert and Ackermann challenged mathematicians to solve the third goal:

Is there a general algorithm that can decide, for any mathematical statement, whether it is provable from the axioms?

In 1936, Alan Turing answered this question by proving that the Halting Problem is undecidable.

This serves as a counterexample to Hilbert’s Goal 3

The Halting Problem

Turing developed the Turing machine to demonstrate the Halting Problem.

The Halting Problem is to decide whether a given program with a given input halts or loops forever.

  • If a math statement can be written as a sequence of logical steps, then this is equivalent to a program running on a Turing machine.

The Halting Problem

Assumption Suppose there exists an algorithm H that always solves this problem.

H(program, input):
    if program(input) will loop forever:
        return "loops forever"
    else:
        return "halts"
Paradox(program):
    if H(program, program) == "loops forever":
        return "halts"
    else:
        while True:
            do nothing    # loops forever
Hello():
    print("hello world")
Not_a_paradox():
    while True:
        print("hello world")

Evaluating Paradox(Hello)

  1. Paradox(Hello) calls H(Hello, Hello)
  2. H(Hello, Hello) evaluates to “halts”
  3. Therefore, Paradox(Hello) actually loops forever

Evaluating Paradox(Not_a_paradox)

  1. Paradox(Not_a_paradox) calls H(Not_a_paradox, Not_a_paradox)
  2. H(Not_a_paradox, Not_a_paradox) evaluates to “loops forever”
  3. Therefore, Paradox(Not_a_paradox) actually halts

Evaluating Paradox(Paradox)

  1. Paradox(Paradox) calls H(Paradox, Paradox)
  2. Two possibilities:
    • If H returns “halts” → Paradox(Paradox) loops forever → H was wrong.
    • If H returns “loops forever” → Paradox(Paradox) halts → H was wrong.
  • Conclusion: This contradiction shows that H cannot exist, and therefore the Halting Problem is undecidable.